package com.define.ssh.util;

import java.util.ArrayList;
import java.util.List;

public class Combine {

	/*
	 * 设有n个元素，组合数量有2的n次方种。 对 0 到 2的n次方-1 中的每个数，考察其二进制位形式，位数为1代表相应元素加入
	 * 到组合，0则不加入该元素至组合。
	 * 
	 * 取组合方法 参数： list ---- 原始数组 返回： 包含所有组合数组的数组
	 */
	public static List<List<Object>> getCombinations(List<Object> list, Object o) {
		final List<List<Object>> result = new ArrayList<List<Object>>();
		final long n = (long) Math.pow(2, list.size());
		List<Object> combine;
		for (long l = 0L; l < n; l++) {
			combine = new ArrayList<Object>();
			for (int i = 0; i < list.size(); i++) {
				if ((l >>> i & 1) == 1)
					combine.add(list.get(i));
			}
			for (final Object obj : combine) {
				if (obj.equals(o)) {
					result.add(combine);
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		final ArrayList<Object> list = new ArrayList<Object>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);

		final List<List<Object>> result = getCombinations(list, 1);
		System.out.println(list.toString());
		System.out.println(result.toString());

		// String[] a = { "1", "2", "3", "4", "5","6","7"};
		// int num = 5;
		// Combine tp = new Combine();
		// for (String obj : tp.combine(a, num)) {
		// System.out.println(obj);
		// }
	}

	/**
	 * 实现的算法
	 * 
	 * @param a
	 *            数据数组
	 * @param num
	 *            M选N中 N的个数
	 * @return
	 */
	private List<String> combine(String[] a, int num) {
		final List<String> list = new ArrayList<String>();
		final StringBuffer sb = new StringBuffer();
		final String[] b = new String[a.length];
		for (int i = 0; i < b.length; i++) {
			if (i < num) {
				b[i] = "1";
			} else
				b[i] = "0";
		}

		int point = 0;
		int nextPoint = 0;
		int count = 0;
		int sum = 0;
		String temp = "1";
		while (true) {
			// 判断是否全部移位完毕
			for (int i = b.length - 1; i >= b.length - num; i--) {
				if (b[i].equals("1"))
					sum += 1;
			}
			// 根据移位生成数据
			for (int i = 0; i < b.length; i++) {
				if (b[i].equals("1")) {
					point = i;
					sb.append(a[point]);
					sb.append(" ");
					count++;
					if (count == num)
						break;
				}
			}
			// 往返回值列表添加数据
			list.add(sb.toString());

			// 当数组的最后num位全部为1 退出
			if (sum == num) {
				break;
			}
			sum = 0;

			// 修改从左往右第一个10变成01
			for (int i = 0; i < b.length - 1; i++) {
				if (b[i].equals("1") && b[i + 1].equals("0")) {
					point = i;
					nextPoint = i + 1;
					b[point] = "0";
					b[nextPoint] = "1";
					break;
				}
			}
			// 将 i-point个元素的1往前移动 0往后移动
			for (int i = 0; i < point - 1; i++)
				for (int j = i; j < point - 1; j++) {
					if (b[i].equals("0")) {
						temp = b[i];
						b[i] = b[j + 1];
						b[j + 1] = temp;
					}
				}
			// 清空 StringBuffer
			sb.setLength(0);
			count = 0;
		}
		//
		System.out.println("数据长度 " + list.size());
		return list;

	}

}
